{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "初始化Q表完成\n",
      "Q_Table,0\n",
      "episode is 0\n",
      "Normal_start:1\n",
      "80\n",
      "0.923885182923\n",
      "episode is 1\n",
      "Normal_start:1\n",
      "124\n",
      "0.884546042474\n",
      "episode is 2\n",
      "Normal_start:1\n",
      "157\n",
      "0.85615701823\n",
      "episode is 3\n",
      "Normal_start:1\n",
      "201\n",
      "0.819733307238\n",
      "episode is 4\n",
      "Normal_start:1\n",
      "219\n",
      "0.805288500972\n",
      "episode is 5\n",
      "Normal_start:1\n",
      "277\n",
      "0.760473952139\n",
      "episode is 6\n",
      "Normal_start:1\n",
      "300\n",
      "0.743410038475\n",
      "episode is 7\n",
      "Normal_start:1\n",
      "313\n",
      "0.733937413443\n",
      "episode is 8\n",
      "Normal_start:1\n",
      "322\n",
      "0.727451208427\n",
      "episode is 9\n",
      "Normal_start:1\n",
      "362\n",
      "0.699319544163\n",
      "episode is 10\n",
      "Normal_start:1\n",
      "378\n",
      "0.688378195659\n",
      "episode is 11\n",
      "Normal_start:1\n",
      "392\n",
      "0.678947072821\n",
      "episode is 12\n",
      "Normal_start:1\n",
      "404\n",
      "0.670967680056\n",
      "episode is 13\n",
      "Normal_start:1\n",
      "418\n",
      "0.661778606141\n",
      "episode is 14\n",
      "Normal_start:1\n",
      "427\n",
      "0.655938916706\n",
      "episode is 15\n",
      "Normal_start:1\n",
      "438\n",
      "0.648872525029\n",
      "episode is 16\n",
      "Normal_start:1\n",
      "459\n",
      "0.635596092451\n",
      "episode is 17\n",
      "Normal_start:1\n",
      "474\n",
      "0.626282180042\n",
      "episode is 18\n",
      "Normal_start:1\n",
      "483\n",
      "0.62076052514\n",
      "episode is 19\n",
      "Normal_start:1\n",
      "497\n",
      "0.612269453973\n",
      "Q_Table,20\n",
      "episode is 20\n",
      "Normal_start:1\n",
      "507\n",
      "0.606276772778\n",
      "episode is 21\n",
      "Normal_start:1\n",
      "514\n",
      "0.602117410122\n",
      "episode is 22\n",
      "Normal_start:1\n",
      "553\n",
      "0.579469339083\n",
      "episode is 23\n",
      "Normal_start:1\n",
      "575\n",
      "0.567077820119\n",
      "episode is 24\n",
      "Normal_start:1\n",
      "583\n",
      "0.562638976606\n",
      "episode is 25\n",
      "Normal_start:1\n",
      "608\n",
      "0.548994271657\n",
      "episode is 26\n",
      "Normal_start:1\n",
      "620\n",
      "0.542564993219\n",
      "episode is 27\n",
      "Normal_start:1\n",
      "630\n",
      "0.537265882997\n",
      "episode is 28\n",
      "Normal_start:1\n",
      "648\n",
      "0.527860003971\n",
      "episode is 29\n",
      "Normal_start:1\n",
      "678\n",
      "0.512554927858\n",
      "episode is 30\n",
      "Normal_start:1\n",
      "697\n",
      "0.503096523607\n",
      "episode is 31\n",
      "Normal_start:1\n",
      "713\n",
      "0.495269760306\n",
      "episode is 32\n",
      "Normal_start:1\n",
      "728\n",
      "0.488045034806\n",
      "episode is 33\n",
      "Normal_start:1\n",
      "736\n",
      "0.484235931257\n",
      "episode is 34\n",
      "Normal_start:1\n",
      "746\n",
      "0.479517204899\n",
      "episode is 35\n",
      "Normal_start:1\n",
      "766\n",
      "0.470220141336\n",
      "episode is 36\n",
      "Normal_start:1\n",
      "780\n",
      "0.463821951192\n",
      "episode is 37\n",
      "Normal_start:1\n",
      "795\n",
      "0.457065422573\n",
      "episode is 38\n",
      "Normal_start:1\n",
      "802\n",
      "0.453946892206\n",
      "episode is 39\n",
      "Normal_start:1\n",
      "811\n",
      "0.449969296207\n",
      "Q_Table,40\n",
      "episode is 40\n",
      "Normal_start:1\n",
      "825\n",
      "0.44385264254\n",
      "episode is 41\n",
      "Normal_start:1\n",
      "835\n",
      "0.439535736619\n",
      "episode is 42\n",
      "Normal_start:1\n",
      "843\n",
      "0.436113159289\n",
      "episode is 43\n",
      "Normal_start:1\n",
      "861\n",
      "0.428511740429\n",
      "episode is 44\n",
      "Normal_start:1\n",
      "869\n",
      "0.425177003239\n",
      "episode is 45\n",
      "Normal_start:1\n",
      "879\n",
      "0.421045923033\n",
      "episode is 46\n",
      "Normal_start:1\n",
      "885\n",
      "0.418587031546\n",
      "episode is 47\n",
      "Normal_start:1\n",
      "900\n",
      "0.412503963143\n",
      "episode is 48\n",
      "Normal_start:1\n",
      "907\n",
      "0.409696273779\n",
      "episode is 49\n",
      "Normal_start:1\n",
      "918\n",
      "0.405323707969\n",
      "episode is 50\n",
      "Normal_start:1\n",
      "927\n",
      "0.401781757284\n",
      "episode is 51\n",
      "Normal_start:1\n",
      "937\n",
      "0.397883463665\n",
      "episode is 52\n",
      "Normal_start:1\n",
      "944\n",
      "0.395177760428\n",
      "episode is 53\n",
      "Normal_start:1\n",
      "952\n",
      "0.39210863123\n",
      "episode is 54\n",
      "Normal_start:1\n",
      "966\n",
      "0.386796382898\n",
      "episode is 55\n",
      "Normal_start:1\n",
      "973\n",
      "0.384168018227\n",
      "episode is 56\n",
      "Normal_start:1\n",
      "981\n",
      "0.381186615592\n",
      "episode is 57\n",
      "Normal_start:1\n",
      "987\n",
      "0.378966163915\n",
      "episode is 58\n",
      "Normal_start:1\n",
      "994\n",
      "0.376392419383\n",
      "episode is 59\n",
      "Normal_start:1\n",
      "1001\n",
      "0.373836628153\n",
      "Q_Table,60\n",
      "episode is 60\n",
      "Normal_start:1\n",
      "1009\n",
      "0.370937546914\n",
      "episode is 61\n",
      "Normal_start:1\n",
      "1019\n",
      "0.367346158316\n",
      "episode is 62\n",
      "Normal_start:1\n",
      "1025\n",
      "0.365208500752\n",
      "episode is 63\n",
      "Normal_start:1\n",
      "1033\n",
      "0.362378169167\n",
      "episode is 64\n",
      "Normal_start:1\n",
      "1046\n",
      "0.357826900313\n",
      "episode is 65\n",
      "Normal_start:1\n",
      "1061\n",
      "0.352648432413\n",
      "episode is 66\n",
      "Normal_start:1\n",
      "1073\n",
      "0.348561223524\n",
      "episode is 67\n",
      "Normal_start:1\n",
      "1083\n",
      "0.345192483064\n",
      "episode is 68\n",
      "Normal_start:1\n",
      "1095\n",
      "0.341194210879\n",
      "episode is 69\n",
      "Normal_start:1\n",
      "1103\n",
      "0.338555227201\n",
      "episode is 70\n",
      "Normal_start:1\n",
      "1111\n",
      "0.33593727117\n",
      "episode is 71\n",
      "Normal_start:1\n",
      "1117\n",
      "0.333987502698\n",
      "episode is 72\n",
      "Normal_start:1\n",
      "1123\n",
      "0.332049397811\n",
      "episode is 73\n",
      "Normal_start:1\n",
      "1134\n",
      "0.328526267178\n",
      "episode is 74\n",
      "Normal_start:1\n",
      "1145\n",
      "0.325041678613\n",
      "episode is 75\n",
      "Normal_start:1\n",
      "1154\n",
      "0.322219024501\n",
      "episode is 76\n",
      "Normal_start:1\n",
      "1163\n",
      "0.319421660302\n",
      "episode is 77\n",
      "Normal_start:1\n",
      "1175\n",
      "0.315730789891\n",
      "episode is 78\n",
      "Normal_start:1\n",
      "1182\n",
      "0.313598147319\n",
      "episode is 79\n",
      "Normal_start:1\n",
      "1193\n",
      "0.310276868223\n",
      "Q_Table,80\n",
      "episode is 80\n",
      "Normal_start:1\n",
      "1200\n",
      "0.308182269793\n",
      "episode is 81\n",
      "Normal_start:1\n",
      "1211\n",
      "0.304920238887\n",
      "episode is 82\n",
      "Normal_start:1\n",
      "1217\n",
      "0.303156015417\n",
      "episode is 83\n",
      "Normal_start:1\n",
      "1226\n",
      "0.300529448559\n",
      "episode is 84\n",
      "Normal_start:1\n",
      "1232\n",
      "0.298791490954\n",
      "episode is 85\n",
      "Normal_start:1\n",
      "1239\n",
      "0.296777009428\n",
      "episode is 86\n",
      "Normal_start:1\n",
      "1248\n",
      "0.294207596047\n",
      "episode is 87\n",
      "Normal_start:1\n",
      "1260\n",
      "0.290817486235\n",
      "episode is 88\n",
      "Normal_start:1\n",
      "1270\n",
      "0.288023305561\n",
      "episode is 89\n",
      "Normal_start:1\n",
      "1277\n",
      "0.286083938127\n",
      "episode is 90\n",
      "Normal_start:1\n",
      "1292\n",
      "0.281973583781\n",
      "episode is 91\n",
      "Normal_start:1\n",
      "1298\n",
      "0.280346628027\n",
      "episode is 92\n",
      "Normal_start:1\n",
      "1307\n",
      "0.27792442464\n",
      "episode is 93\n",
      "Normal_start:1\n",
      "1313\n",
      "0.276321691101\n",
      "episode is 94\n",
      "Normal_start:1\n",
      "1321\n",
      "0.274199617185\n",
      "episode is 95\n",
      "Normal_start:1\n",
      "1332\n",
      "0.271309347025\n",
      "episode is 96\n",
      "Normal_start:1\n",
      "1342\n",
      "0.26870927558\n",
      "episode is 97\n",
      "Normal_start:1\n",
      "1348\n",
      "0.267161667394\n",
      "episode is 98\n",
      "Normal_start:1\n",
      "1354\n",
      "0.265623317055\n",
      "episode is 99\n",
      "Normal_start:1\n",
      "1362\n",
      "0.263586488695\n",
      "[[ 1.27157213  2.60536668  5.75829619  1.66775192]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 2.98030254  1.74796715  6.49927964  2.12789982]\n",
      " [ 0.          0.          0.          0.        ]\n",
      " [ 5.64312832  6.07963805  5.64367618  9.99973439]\n",
      " [ 3.57177271  7.26741242  3.94049612  3.83335487]\n",
      " [ 5.3579413   8.09205665  3.73183013  5.34305098]\n",
      " [ 5.09104229  5.11605488  5.45863193  8.99812972]]\n",
      "4\n",
      "7\n",
      "8\n",
      "9\n",
      "6\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "%matplotlib qt5\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "Alpha=0.1 #学习速率\n",
    "Beta=0.9 #对未来奖励的衰减度\n",
    "Epsilon_start=1#选择随机动作的概率 Epsilon\n",
    "Epsilon_stop=0.01\n",
    "decay_rate=0.001\n",
    "N_Mesh=3\n",
    "N_States=9\n",
    "Actions=['left','right','up','down']\n",
    "Obstacle=[2,5]\n",
    "#——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Caculate_coordinate(State):\n",
    "    X_Axis=0.5+(State-1)%N_Mesh\n",
    "    Y_Axis=0.5+((State-1)//N_Mesh)\n",
    "    return X_Axis,Y_Axis\n",
    "def Initial_Q_Table (N_States,Actions):#以状态数和动作为变量，返回Q表\n",
    "    Q_Table=np.zeros([N_States,len(Actions)])#初始化Q_表\n",
    "    Q_Table=pd.DataFrame(Q_Table,index=np.arange(1,N_States+1),columns=Actions)#Q_表定义行列标签\n",
    "    print ('初始化Q表完成') \n",
    "    return Q_Table\n",
    "#——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Select_Action(State,Q_Table,ep):#根据目前的状态选择动作,返回执行动作\n",
    "    Epsilon=Epsilon_stop+(Epsilon_start-Epsilon_stop)*np.exp(-decay_rate*ep)\n",
    "    States_Actions=Q_Table.loc[[State],:]#选择目前状态下，取出Q表的目前的状态行,state选择为数字\n",
    "    if(np.random.rand()<Epsilon or np.all(States_Actions==[0])):#其实np.all(States_Action==[0])也行\n",
    "        Execute_Action=np.random.choice(Actions)\n",
    "    else:\n",
    "        #Q_T=Q_Table.T\n",
    "        #G=(Q_Table.T).loc[:,[State]]\n",
    "        Execute_Action=np.array(pd.DataFrame.idxmax((Q_Table.T).loc[:,[State]]))[0]#这里真心累，有毒\n",
    "    return Execute_Action\n",
    "#———————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Next_State(State,Execute_Action):#根据目前状态个选择的动作,返回即时奖励和新状态\n",
    "    if(Execute_Action=='left'):\n",
    "        #目标在右上角，如果Execute_Action为‘left’，不可能到达目标\n",
    "        if(State%N_Mesh==1):#判断是不是在网格最左边\n",
    "            State=State\n",
    "            R=-1\n",
    "        elif((State-1) in Obstacle):\n",
    "            State=State\n",
    "            R=-1\n",
    "        else:\n",
    "            State=State-1\n",
    "            R=0\n",
    "    elif(Execute_Action=='right'):\n",
    "        if(State==N_Mesh-1):\n",
    "            State='End'\n",
    "            R=10\n",
    "        elif(State%N_Mesh==0):\n",
    "            State=State\n",
    "            R=-1\n",
    "        elif((State+1) in Obstacle):\n",
    "            State=State\n",
    "            R=-1\n",
    "        else:\n",
    "            State=State+1\n",
    "            R=0\n",
    "    elif(Execute_Action=='up'):  \n",
    "        if(N_States+1-N_Mesh<=State<=N_States):\n",
    "            State=State\n",
    "            R=-1\n",
    "        elif((State+N_Mesh) in Obstacle):\n",
    "            State=State\n",
    "            R=-1\n",
    "        else:\n",
    "            State=State+N_Mesh\n",
    "            R=0\n",
    "    else:\n",
    "        if(State-N_Mesh==3):\n",
    "            State='End'\n",
    "            R=10\n",
    "        elif(0<=State<=N_Mesh):\n",
    "            State=State\n",
    "            R=-1\n",
    "        elif((State-N_Mesh) in Obstacle):\n",
    "            State=State\n",
    "            R=-1\n",
    "        else:\n",
    "            R=0\n",
    "            State=State-N_Mesh\n",
    "    return State,R\n",
    "        \n",
    "#————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Run_Function():\n",
    "    #——————————————————————————————————————————————————画图程序部分\n",
    "    \n",
    "    \n",
    "    #——————————————————————————————————————————————————\n",
    "    Q_Table=Initial_Q_Table (N_States,Actions)\n",
    "    Step=0 \n",
    "    for episode in np.arange(100) :#跑20回合\n",
    "        if(episode%20==0):\n",
    "            print('Q_Table,%d'%episode)\n",
    "            Q_Table\n",
    "#         fig=plt.figure()\n",
    "#         ax=fig.gca()\n",
    "#         ax.set(xlim=[0, N_Mesh], ylim=[0, N_Mesh])\n",
    "#         ax.set_xticks(np.arange(0,(N_Mesh+1)))\n",
    "#         ax.set_yticks(np.arange(0,(N_Mesh+1)))\n",
    "#         plt.grid()\n",
    "        print('episode is %d' % episode)\n",
    "        State_=1 #定义起点 \n",
    "        print(\"Normal_start:%d\"%State_)\n",
    "        Is_End=False\n",
    "        while not Is_End:\n",
    "            A=Select_Action(State_,Q_Table,Step)\n",
    "            Next_S,R=Next_State(State_,A)\n",
    "            Q_Table_S_A=Q_Table.loc[[State_],[A]]\n",
    "            if Next_S!='End':\n",
    "                D_T=np.array((Q_Table.loc[[Next_S],:]).T)\n",
    "                Q_Target=R+Beta*D_T.max() #Next_S状态中的可选动作中的最大Q值动作\n",
    "                Step+=1\n",
    "            else:\n",
    "                Q_Target=R\n",
    "                Step+=1\n",
    "                Is_End=True #目的是结束循\n",
    "#————————————————————————————————————————————————————————————————————————————画图程序\n",
    "#             X_State,Y_State=Caculate_coordinate(State_)\n",
    "#             if(Next_S)=='End':\n",
    "#                 H=N_States\n",
    "#             else:\n",
    "#                 H=Next_S\n",
    "#             X_Next_State,Y_Next_State=Caculate_coordinate(H)                      \n",
    "#             if(Step==0):\n",
    "#                 plt.scatter(X_State,Y_State)  \n",
    "#             else:\n",
    "#                 plt.scatter(X_State,Y_State) \n",
    "#                 plt.scatter(X_Next_State,Y_Next_State)\n",
    "#                 plt.plot([X_State,X_Next_State],[Y_State,Y_Next_State])\n",
    "#————————————————————————————————————————————————————————————————————————————\n",
    "            Q_Table.loc[[State_],[A]]+=Alpha*(Q_Target-Q_Table_S_A)\n",
    "            State_=Next_S\n",
    "        print(Step)\n",
    "        print(Epsilon_stop+(Epsilon_start-Epsilon_stop)*np.exp(-decay_rate*Step))\n",
    "        #plt.show()\n",
    "        #print(Q_Table)\n",
    "    return Q_Table\n",
    "#————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "Q__Table=Run_Function()\n",
    "Q__Table\n",
    "Final_Q_Table=np.array(Q__Table)\n",
    "#—————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "def Plot_Final_Graph(Q_TABLE):\n",
    "    f=open('A.txt','w+')\n",
    "    f.write(str(Q_TABLE))\n",
    "    f.close()\n",
    "    print(Q_TABLE)\n",
    "    fig=plt.figure()\n",
    "    ax=fig.gca()\n",
    "    ax.set(xlim=[0, N_Mesh], ylim=[0, N_Mesh])\n",
    "    ax.set_xticks(np.arange(0,(N_Mesh+1)))\n",
    "    ax.set_yticks(np.arange(0,(N_Mesh+1)))\n",
    "    plt.grid()\n",
    "    State_Start=1\n",
    "    State=State_Start\n",
    "    Step=1\n",
    "    while(State!=N_Mesh):\n",
    "        Action=np.argmax((Q_TABLE[State-1]))\n",
    "        if(Action==0):\n",
    "             Next_State=State-1\n",
    "        elif(Action==1):\n",
    "             Next_State=State+1\n",
    "        elif(Action==2):\n",
    "             Next_State=State+N_Mesh\n",
    "        else:\n",
    "             Next_State=State-N_Mesh\n",
    "        Step+=1\n",
    "        print(Next_State)\n",
    "        X_State,Y_State=Caculate_coordinate(State)\n",
    "        X_Next_State,Y_Next_State=Caculate_coordinate(Next_State)\n",
    "        if(Step==0):\n",
    "            plt.scatter(X_State,Y_State)  \n",
    "        else:\n",
    "            plt.scatter(X_State,Y_State) \n",
    "            plt.scatter(X_Next_State,Y_Next_State)\n",
    "            plt.plot([X_State,X_Next_State],[Y_State,Y_Next_State])\n",
    "        for J in np.arange(len(Obstacle)):\n",
    "            plt.scatter((Caculate_coordinate(Obstacle[J]))[0],(Caculate_coordinate(Obstacle[J]))[1],marker=\"x\",s=300)\n",
    "        State=Next_State\n",
    "    plt.show()\n",
    "#——————————————————————————————————————————————————————————————————————————————————————————————————————————\n",
    "Plot_Final_Graph(Final_Q_Table)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
